//给你一个大小为 m x n 的网格和一个球。球的起始坐标为 [startRow, startColumn] 。你可以将球移到在四个方向上相邻的单元格内（可以
//穿过网格边界到达网格之外）。你 最多 可以移动 maxMove 次球。
//
// 给你五个整数 m、n、maxMove、startRow 以及 startColumn ，找出并返回可以将球移出边界的路径数量。因为答案可能非常大，返回对
//10⁹ + 7 取余 后的结果。
//
//
//
// 示例 1：
//
//
//输入：m = 2, n = 2, maxMove = 2, startRow = 0, startColumn = 0
//输出：6
//
//
// 示例 2：
//
//
//输入：m = 1, n = 3, maxMove = 3, startRow = 0, startColumn = 1
//输出：12
//
//
//
//
// 提示：
//
//
// 1 <= m, n <= 50
// 0 <= maxMove <= 50
// 0 <= startRow < m
// 0 <= startColumn < n
//
//
// Related Topics 动态规划 👍 306 👎 0

package leetcode.editor.cn;
//java:出界的路径数
public class Q0576OutOfBoundaryPaths {
    public static void main(String[] args){
        Solution solution = new Q0576OutOfBoundaryPaths().new Solution();
        solution.findPaths(1, 3, 3, 0, 1);
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    // 保存 i，j 位置开始k步以内的路径数量
    int[][][] cached;
    int mod = 1000000007;
    int[][] directions = {{0, -1}, {0,  1}, {-1,  0}, {1, 0}};
    public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
//        if (maxMove <= 0) return 0;
//        cached = new int[m][n][maxMove + 1];
//        // 初始化
//        for (int i = 0; i < m; i++) {
//            for (int j = 0; j < n; j++) {
//                for (int k = 0; k < maxMove + 1; k++) {
//                    cached[i][j][k] = -1;
//                }
//            }
//        }
//
//        int res = 0;
//        for (int i = 1; i < maxMove + 1; i++) {
//            res +=  dfs(m, n, i, startRow, startColumn);
//            res %= mod;
//        }
//        return res;

        int[][][] dp = new int[m][n][maxMove + 1];


        for (int k = 1; k < maxMove + 1; k++) {
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
                    int sum1 = 0;
                    sum1 += i == 0 ? 1 : 0;
                    sum1 += i == m - 1 ? 1 : 0;
                    sum1 += j == 0 ? 1 : 0;
                    sum1 += j == n - 1 ? 1 : 0;
                    dp[i][j][k] = sum1;
                }

                }
            }
        }

        for (int k = 1; k < maxMove + 1; k++) {
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    // 尝试四个方向
                    for (int[] direction : directions) {
                        // 当前尝试的下一个点还在格子内
                        if (i + direction[0] >=0 && i + direction[0] < m
                                && j + direction[1] >= 0 && j + direction[1] < n) {
                            dp[i][j][k] = dp[i][j][k] + dp[i + direction[0]][j + direction[1]][k - 1];
                            dp[i][j][k] %= mod;
                        }
                    }
                }
            }
        }
        return dp[startRow][startColumn][maxMove];
    }

//    public int dfs(int m, int n, int maxMove, int startRow, int startColumn) {
//        // 超出边界
//        if (startRow < 0 || startRow >= m || startColumn < 0 || startColumn >= n) return 0;
//        // 备忘录中有值
//        if (cached[startRow][startColumn][maxMove] != -1) return cached[startRow][startColumn][maxMove];
//
//        // Base case2: 边界的情况
//        if (maxMove == 1 && (startRow == 0 || startRow == m - 1 || startColumn == 0 || startColumn == n - 1)) {
//            int sum1 = 0;
//            sum1 += startRow == 0 ? 1 : 0;
//            sum1 += startRow == m - 1 ? 1 : 0;
//            sum1 += startColumn == 0 ? 1 : 0;
//            sum1 += startColumn == n - 1 ? 1 : 0;
//            cached[startRow][startColumn][maxMove] = sum1;
//            return sum1;
//        }
//
//        // Base case2: 剩余步数无法到达外界
//        int minDis = Math.min(startColumn + 1, startRow + 1);
//        minDis = Math.min(minDis, m - startRow);
//        minDis = Math.min(minDis, n - startColumn);
//        if (minDis > maxMove) {
//            cached[startRow][startColumn][maxMove] = 0;
//            return 0;
//        }
//
//        int sum = 0;
//        // 回溯搜索四个方向
//        for (int i = 0; i < 4; i++) {
//            sum += dfs(m, n, maxMove - 1, startRow + directions[i][0], startColumn + directions[i][1]);
//            sum %= mod;
//        }
//        cached[startRow][startColumn][maxMove] = sum;
//        return sum;
//    }
}
//leetcode submit region end(Prohibit modification and deletion)

}